package CodingTest;
/**
 * 思路整理：
 * 1，首先定义一个一维整数数组用于存放每一列皇后所在的行号a[0] = 0
 *    表示第0列的皇后放在了第0行
 * 2，循环8次，将第0列的皇后从0行一直循环放到7行，递归摆放其他列
 * 3，如果8列都摆放上了皇后，摆放方法计数器加一，打印当前摆放方法
 * 4，在8次循环中，从第0行开始判断是否满足当前行号m-a[i] == 0即
 *    与之前的皇后在同一行，m-a[i] == n-i(n表示当前列号)即与之
 *    前的皇后在对角线，满足一项则该行不能放皇后，找到可以放皇后
 *    的位置后递归下一列，如果8行都不能放，则回溯到上一列把皇后
 *    位置向下放到满足条件的位置
 *    **/
public class EightQueen {
    //皇后的个数
    public final static int MAXQUEEN = 8;
    //皇后摆放方法的个数
    public static int num = 0;
    //每一列的皇后在该列的行号
    public static int[] cols = new int[MAXQUEEN];
    /***
     * n 当前列号
     */
public static void getCount(int n ){
    //如果8列都当上了皇后，则是先了一种摆放方法
    if(n == MAXQUEEN){
        num++;
        System.out.println("第"+num+"种摆放方法：");
        printQueen();

    }
    //m代表的是行号
    for(int m = 0;m<MAXQUEEN;m++){
        //如果是第一列，则皇后摆放无限制，可以从0行到最后一行随便放
        if(n == 0){
            cols[0] = m;
            getCount(n+1);
        }else{
            int i = 0;
            //遍历之前所有摆放皇后的位置
            for(;i<n;i++){
                //1,如果当前行号与之前摆放皇后的行号差值为0则在同一行不能摆放，
                //2,行的差值与列的差值相等则在对角线上不能摆放
                int d = Math.abs(m - cols[i]);
                if(d == 0|| d == n-i)
                    break;
            }
            //如果i与n相等代表当前的m行可以放皇后，不与前面的皇后位置冲突
            //i表示列数，n表示当前列数
            if(i==n) {
                cols[n] = m;
                getCount(n+1);
            }

        }
    }
}
public static void printQueen(){

        for(int i = 0;i<MAXQUEEN;i++){
            for(int j = 0;j<MAXQUEEN;j++){
                if(cols[j] == i){
                    System.out.print("0");
                }else{
                    System.out.print("+");
                }
            }
            System.out.println("");
        }


    }
    public static void main(String[] args){
        getCount(0);
}
}
